/****************************************************************************
 * Elisa 1.0                                                                *
 *--------------------------------------------------------------------------*
 * Author: Laurent Granvilliers, Vincent Sorin                              *
 * Copyright (c) 2004 Laboratoire d'Informatique de Nantes Atlantique       *
 *--------------------------------------------------------------------------*
 * Elisa is distributed WITHOUT ANY WARRANTY. Read the associated           *
 * COPYRIGHT file for more details.                                         *
 *--------------------------------------------------------------------------*
 * elisa_heap.h                                                             *
 ****************************************************************************/

/**
 * @file elisa_heap.h
 * @brief Classes for domain and search heap management.
 */

/**
 * @defgroup Domain Domain
 * @brief Classes for domain and search heap management.
 */


#ifndef _ELISA_HEAP_H
#define _ELISA_HEAP_H

#include <iostream>
#include <cstring>
#include <memory>
#include "elisa_defs.h"
#include "elisa_domain.h"

NAMESPACE_ELISA

/**
 * @ingroup Domain
 * @class Box
 * @brief A box is a list of domains
 */
class Box
{
public:
	/**
 	 * Constructor
 	 * @param val the value to copy in the box
 	 * @param size the size of the value
 	 */
	Box (char *val, size_t size)
	: m_val(std::auto_ptr<char>(new char[size])),
	  m_size(size)
	{
		memcpy(m_val.get(), val, size);
	}

	/**
 	 * Copy constructor
 	 */
	Box (const Box & b)
	: m_val(std::auto_ptr<char>(new char[b.m_size])),
	  m_size(b.m_size)
	{
		memcpy(m_val.get(), b.m_val.get(), m_size);
	}

	/**
 	 * Destructor
 	 */
	~Box ()
	{
		//delete[] m_val;
	}

	/**
 	 * Give the value stocked in the box
 	 * @return a pointer to the value
 	 */
	char *value()
	{
		return m_val.get();
	}


	/**
 	 * give the size of the box
 	 * @return the size
 	 */
	size_t size()
	{
		return m_size;
	}

private:
	//char *m_val;				// value
	std::auto_ptr<char> m_val;	// value
	size_t m_size;				// size

	/// Copy protection
	Box & operator=(const Box & b) {}
};

/**
 * @ingroup Domain
 * @class Heap
 * @brief Heap for boxes generated during search.
 */
class Heap
{
private:
	/**
 	 * The index of a box in the heap:
 	 *   - size: size of the box
 	 *   - adrHeap: pointer to the beginning of the memory zone in the heap
 	 */
	typedef struct 
	{
		size_t size;
		char *adrHeap;
	} 
	IndexBox;

	/**
 	 * The relative index of a domain in a box
 	 *   - size: size of domain
 	 *   - shift: index of domain value wrt. the beginning of the box
 	 */
	typedef struct 
	{
		size_t size;
		int shift;
	}
	IndexDomain;

public:
	/// Exception class
	class HeapOverflow { };

	/// Exception class
	class HeapDomainOverflow { };

	/**
 	 * Constructor
 	 * @param dfs true if you use the dfs strategy
 	 * @param size the total size of the heap
 	 * @param max the maximum number of boxes authorized in the box
 	 */
	Heap (bool dfs = true,
	      const long & size = DefaultHeapSize,
	      const long & max = DefaultMaxBox)
	: m_dfs(dfs),
	  m_sizeHeap(size),
	  m_sizeBox(max),
	  m_heap(std::auto_ptr<char>(new char[size])),
	  m_box(std::auto_ptr<IndexBox>(new IndexBox[max])),
	  m_firstBox(0), m_lastBox(-1), m_numBox(0)
	{
	}

	/**
 	 * Constructor
 	 * @param size the total size of the heap
 	 * @param max the maximum number of boxes authorized in the box
 	 */
	Heap (const long & size = DefaultHeapSize,
	      const long & max = DefaultMaxBox)
	: m_dfs(true),
	  m_sizeHeap(size),
	  m_sizeBox(max),
	  m_heap(std::auto_ptr<char>(new char[size])),
	  m_box(std::auto_ptr<IndexBox>(new IndexBox[max])),
	  m_firstBox(0), m_lastBox(-1), m_numBox(0)
	{
	}

	/**
 	 * Destructor
 	 */
	virtual ~Heap ()
	{
		//delete[] m_box;
		//delete[] m_heap;
	}

	/// @name Modification of strategy
	//@{
	void setDFS()
	{
		m_dfs = true;
	}

	void setBFS()
	{
		m_dfs = false;
	}
	//@}

	/**
 	 * Return the number of boxes in the heap
 	 */
	long numBox() const
	{
		return m_numBox;
	}

	/**
 	 * tell if the heap is empty
 	 * @return true if numBox()==0
 	 */
	bool isEmpty() const
	{
		return m_numBox == 0;
	}

	/**
 	 * tell if the heap is full
 	 * @return true if numBox()==max give in constructor
 	 */
	bool isFull() const
	{
		return m_numBox == m_sizeBox;
	}

	/**
 	 * Give the number of free boxes
 	 * @return max give in constructor - the number of allocated boxes
 	 */
	long numFreeBoxes() const
	{
		return m_sizeBox - m_numBox;
	}

	/**
 	 * Return the address of the beginning of the current box
 	 * @return a pointer to the box
 	 */
	char *adrCurrentBox() const
	{
		return m_box.get()[m_lastBox].adrHeap;
	}

	/**
 	 * Return the size of the current box
 	 */
	size_t sizeCurrentBox() const
	{
		return m_box.get()[m_lastBox].size;
	}

	/**
 	 * Remove the current box
 	 */
	void discardBox()
	{
		if (--m_lastBox == -1) {
			m_lastBox = m_sizeBox - 1;
		}
		--m_numBox;
	}

	/**
 	 * Return a copy of the current box
 	 * @return a box with the same value of the current box
 	 */
	Box *copyBox() const
	{
		return new Box(m_box.get()[m_lastBox].adrHeap, m_box.get()[m_lastBox].size);
	}

	/**
 	 * Return a copy of the current box
 	 * @return a box with the same value of the current box
 	 */
	Box *copyBox(long numBox) const
	{
		return new Box(m_box.get()[numBox].adrHeap, m_box.get()[numBox].size);
	}
	/**
 	 * @brief add a box in the heap
 	 *
 	 * b becomes the current box in the heap
 	 * @param b the box to add
 	 */
	void addBox(Box *b) throw (HeapOverflow)
	{
		copyBoxToBack(b->value(), b->size());
	}

	/**
 	 * Allocation of a new domain of size n at the end of the heap
 	 * @return the index of domain in the heap
 	 */
	long allocate(size_t n) throw (HeapDomainOverflow);

	/**
 	 * Allocation of a new domain of type D at the end of the heap
 	 * @return the index of domain in the heap
 	 */
	template<class D>
	long allocate() throw (HeapDomainOverflow)
	{
		return allocate(sizeof(D));
	}

	/**
 	 * Modification of the current domain at address adr
 	 * @param adr address of the old domain
 	 * @param size the size of the domain
 	 * @param dom the new domain
 	 */
	void setDomain(long adr,
	               const void *dom,
	               size_t size) const
	{
		memcpy(valueDomain(adr, m_lastBox), dom, size);
	}

	/**
 	 * Modification of the current domain at address adr
 	 * @param adr address of the old domain
 	 * @param size the size of the domain
 	 * @param dom the new domain
 	 */
	void setDomain(long adr,
	               const void *dom,
	               size_t size,
	               Box *b) const
	{
		memcpy(valueDomain(adr, b), dom, size);
	}

	/**
 	 * Modification of the current domain at address adr
 	 * @param adr address of the old domain
 	 * @param dom the new domain
 	 */
	template<class D>
	void setDomain(long adr,
	               const D & dom) const
	{
		memcpy(valueDomain(adr, m_lastBox), &dom, sizeof(D));
		//memcpy(valueDomain(adr), &dom, sizeof(D));
	}

	/**
 	 * Modification of the current domain at address adr
 	 * @param adr address of the old domain
 	 * @param box the number of the box
 	 * @param dom the new domain
 	 */
	template<class D>
	void setDomain(long adr,
	               long box,
	               const D & dom) const
	{
		memcpy(valueDomain(adr, box), &dom, sizeof(D));
	}

	/**
 	 * Modification of the current domain at address adr
 	 * @param adr address of the old domain
 	 * @param b the box
 	 * @param dom the new domain
 	 */
	template<class D>
	void setDomain(long adr,
	               Box *b,
	               const D & dom) const
	{
		memcpy(valueDomain(adr, b), &dom, sizeof(D));
	}

	/// @name Return the current domain
	//@{

	/**
 	 * @param adr the address of the domain in the current box
 	 */
	template<class D>
	const D & const_domain(long adr) const
	{
		return *(static_cast<D *>(valueDomain(adr, m_lastBox)));
	}

	/**
 	 * @param adr the address of the domain in the box
 	 * @param box the number of the box to use
 	 */
	template<class D>
	const D & const_domain(long adr, long box) const
	{
		return *(static_cast<D *>(valueDomain(adr, box)));
	}

	/**
 	 * @param adr the address of the domain in the current box
 	 * @param b the box to use
 	 */
	template<class D>
	const D & const_domain(long adr, Box *b) const
	{
		return *(static_cast<D *>(valueDomain(adr, b)));
	}
	//@}

	/// @name Return the current domain
	//@{
	/**
 	 * @param adr the address of the domain in the current box
 	 */
	template<class D>
	D *domain(long adr)
	{
		return static_cast<D *>(valueDomain(adr, m_lastBox));
	}

	/**
 	 * @param adr the address of the domain in the box
 	 * @param box the number of the box to use
 	 */
	template<class D>
	D *domain(long adr, long box)
	{
		return static_cast<D *>(valueDomain(adr, box));
	}

	/**
 	 * @param adr the address of the domain in the current box
 	 * @param b the box to use
 	 */
	template<class D>
	D *domain(long adr, Box *b)
	{
		return static_cast<D *>(valueDomain(adr, b));
	}
	//@}

	/**
 	 * Creates a copy of the box at the end of the heap
 	 * @param adrHeap a pointer to the box to copy
 	 * @param size the size of the box
 	 */
	long copyCurrentBoxToBack()
	{
		return copyBoxToBack(m_box.get()[m_lastBox].adrHeap, m_box.get()[m_lastBox].size);
	}

	/**
 	 * Creates a copy of the box at the end of the heap
 	 * @param adrHeap a pointer to the box to copy
 	 * @param size the size of the box
 	 */
	long copyBoxToBack(char *adrHeap, size_t size) throw (HeapOverflow);


	/**
 	 * Creates a copy of the box at the front of the heap
 	 * @param adrHeap a pointer to the box to copy
 	 * @param size the size of the box
 	 */
	void copyBoxToFront(char *adrHeap, size_t size) throw (HeapOverflow);

	/// @name Splitting methods wrt. the search strategy associated to the heap
	//@{
	template<class D>
	void splitBox(long adr,
	              const D & dom1,
	              const D & dom2)
	{
		(m_dfs ? splitBoxToBack<D>(adr, dom1, dom2) :
		 splitBoxToFront<D>(adr, dom1, dom2));
	}

	template<class D>
	void splitBox(long adr,
	              const D *doms,
	              int n)
	{
		(m_dfs ? splitBoxToBack<D>(adr, doms, n) :
		 splitBoxToFront<D>(adr, doms, n));
	}
	//@}

	/**
 	 * @name Splitting methods for Depth-First Search
 	 * The domain at address adr is split in two domains dom1 and dom2.
 	 * The current box is removed.
 	 * Two boxes are added at the top of the heap in the following order:
 	 *   <ul>
 	 *   <li> a copy of the old current box where the domain at address
 	 *        adr takes value dom2;
 	 *   <li> a copy of the old current box where the domain at address
 	 *        adr takes value dom1. This box becomes the current box.
 	 *   </ul>
 	 */
	//@{
	template<class D>
	void splitBoxToBack(long adr,
	                    const D & dom1,
	                    const D & dom2)
	{
		setDomain<D>(adr, dom2);
		copyBoxToBack(m_box.get()[m_lastBox].adrHeap, m_box.get()[m_lastBox].size);
		setDomain<D>(adr, dom1);
	}

	template<class D>
	void splitBoxToBack(long adr,
	                    const D *doms,
	                    int n)
	{
		setDomain<D>(adr, doms[n - 1]);
		for (int i = n - 2; i >= 0; --i) {
			copyBoxToBack(m_box.get()[m_lastBox].adrHeap, m_box.get()[m_lastBox].size);
			setDomain<D>(adr, doms[i]);
		}
	}
	//@}



	/// @name Splitting methods for Breadth-First Search
	//@{
	template<class D>
	void splitBoxToFront(long adr,
	                     const D & dom1,
	                     const D & dom2)
	{
		copyBoxToFront(m_box.get()[m_lastBox].adrHeap, m_box.get()[m_lastBox].size);
		setDomain<D>(adr, m_firstBox, dom2);
		copyBoxToFront(m_box.get()[m_lastBox].adrHeap, m_box.get()[m_lastBox].size);
		setDomain<D>(adr, m_firstBox, dom1);
		discardBox();
	}

	template<class D>
	void splitBoxToFront(long adr,
	                     const D *doms,
	                     int n)
	{
		for (int i = n - 1; i >= 0; --i) {
			copyBoxToFront(m_box.get()[m_lastBox].adrHeap, m_box.get()[m_lastBox].size);
			setDomain<D>(adr, m_firstBox, doms[i]);
		}
		discardBox();
	}
	//@}

	/// Returns a pointer to the value of domain at address adr
	/// in the current box
	void *valueDomain(long adr) const;

private:
	//char *m_heap;		// the heap
	std::auto_ptr<char> m_heap; // the heap
	long m_sizeHeap;	// total size of the heap

	//IndexBox *m_box;	// the set of indexes of boxes
	std::auto_ptr<IndexBox> m_box; // the set of indexes of boxes
	long m_sizeBox;		// total size of the set of indexes
	long m_firstBox;	// the index of the first box
	long m_lastBox;		// the index of the current box (last one)
	long m_numBox;		// number of boxes

	bool m_dfs;			// true if DFS search, false if BFS

	static const long DefaultHeapSize;	// default size of the heap
	static const long DefaultMaxBox;	// default max number of boxes during search


	/// Returns a pointer to the value of domain at address adr
	/// in the current box
	void *valueDomain(long adr, long box) const;

	/// Returns a pointer to the value of domain at address adr
	/// in the box b
	void *valueDomain(long adr, Box *b) const;
};


/**
 * @ingroup Domain
 * @class HeapStack
 * @brief Heap for boxes generated during search using the DFS strategy
 */
class HeapStack : public Heap 
{
public:
	/// @name Constructors
	//@{
	HeapStack (const long & size,
	           const long & max)
	: Heap(true, size, max)
	{
	}

	HeapStack () 
	: Heap(true)
	{
	}
	//@}

	/// Destructor
	~HeapStack ()
	{
	}
};

/**
 * @ingroup Domain
 * @class HeapQueue
 * @brief Heap for boxes generated during search using the BFS strategy
 */
class HeapQueue : public Heap 
{
public:
	/**
 	 * Constructor
 	 * @param size the total size of the heap
 	 * @param max the maximum number of boxes authorized in the box
 	 */
	HeapQueue (const long & size,
	           const long & max) 
	: Heap(false, size, max)
	{
	}

	/**
 	 * Constructor using the default size and the default max number of box
 	 */
	HeapQueue () 
	: Heap(false)
	{
	}

	/// Destructor
	~HeapQueue ()
	{
	}
};


// Implementation:

inline long Heap::allocate(size_t n) throw (HeapDomainOverflow)
{
	if (m_numBox == 0) {
		m_numBox = 1;
		m_lastBox = 0;
		m_box.get()[0].size = 0;
		m_box.get()[0].adrHeap = m_heap.get();
	}

	size_t domsize = n + sizeof(IndexDomain);
	char *backHeap = m_box.get()[m_lastBox].adrHeap + m_box.get()[m_lastBox].size;

	/// Is the heap full?
	if (backHeap + domsize >= m_heap.get() + m_sizeHeap) {
		throw HeapDomainOverflow();
	}

	IndexDomain index = { n, (backHeap + sizeof(IndexDomain)) - m_box.get()[m_lastBox].adrHeap };
	memcpy(backHeap, &index, sizeof(IndexDomain));
	m_box.get()[m_lastBox].size += domsize;

	// ishii
	//long result = backHeap - m_heap.get();
	long result = backHeap - m_box.get()[m_lastBox].adrHeap;
	return result;
}

inline long Heap::copyBoxToBack(char *adrHeap, size_t size) 
	throw (HeapOverflow)
{
	// Is the list of boxes full?
	if (m_numBox >= m_sizeBox) {
		throw HeapOverflow();
	}
	// Is the list of boxes empty?
	else if (m_numBox == 0) {
		m_firstBox = m_lastBox = 0;
		m_numBox = 1;
		memcpy(m_heap.get(), adrHeap, size);
		m_box.get()[0].size = size;
		m_box.get()[0].adrHeap = m_heap.get();
	}

	// Address in the heap of the next free cell after the last box
	char *backHeap = m_box.get()[m_lastBox].adrHeap + m_box.get()[m_lastBox].size;

	// Two cases for allocation in the heap (empty = free space)
	if (m_box.get()[m_lastBox].adrHeap >= m_box.get()[m_firstBox].adrHeap) {
		// 1. | empty | first | ... | last | empty |

		// allocation at the end?
		if (backHeap + size >= m_heap.get() + m_sizeHeap) {
			// allocation at the beginning?
			backHeap = m_heap.get();
			if (backHeap + size >= m_box.get()[m_firstBox].adrHeap) {
				throw HeapOverflow();
			}
		}
	} else {
		// 2. | ... | last | empty | first | ... |

		// allocation after the last box?
		if (backHeap + size >= m_box.get()[m_firstBox].adrHeap) {
			throw HeapOverflow();
		}
	}

	memcpy(backHeap, adrHeap, size);
	m_lastBox = ((m_lastBox == m_sizeBox - 1) ? 0 : m_lastBox + 1);
	m_box.get()[m_lastBox].size = size;
	m_box.get()[m_lastBox].adrHeap = backHeap;
	++m_numBox;

	return m_lastBox;
}

inline void Heap::copyBoxToFront(char *adrHeap, size_t size) 
	throw (HeapOverflow)
{
	// Is the list of boxes full?
	if (m_numBox >= m_sizeBox) {
		throw HeapOverflow();
	}
	// Is the list of boxes empty?
	else if (m_numBox == 0) {
		m_firstBox = m_lastBox = 0;
		m_numBox = 1;
		memcpy(m_heap.get(), adrHeap, size);
		m_box.get()[0].size = size;
		m_box.get()[0].adrHeap = m_heap.get();
	}


	// Address in the heap of the previous free cell before the first box
	char *frontHeap = m_box.get()[m_firstBox].adrHeap - size;

	// Two cases for allocation in the heap (empty = free space)
	if (m_box.get()[m_lastBox].adrHeap >= m_box.get()[m_firstBox].adrHeap) {
		// 1. | empty | first | ... | last | empty |

		// allocation before the first box?
		if (frontHeap < m_heap.get()) {
			// allocation at the end?
			frontHeap = (m_heap.get() + m_sizeHeap - 1) - size;
			if (frontHeap < m_box.get()[m_lastBox].adrHeap + m_box.get()[m_lastBox].size) {
				throw HeapOverflow();
			}
		}
	} else {
		// 2. | ... | last | empty | first | ... |

		// allocation after the last box?
		if (frontHeap < m_box.get()[m_lastBox].adrHeap + m_box.get()[m_lastBox].size) {
			throw HeapOverflow();
		}
	}

	memcpy(frontHeap, adrHeap, size);
	m_firstBox = ((m_firstBox == 0) ? m_sizeBox - 1 : m_firstBox - 1);
	m_box.get()[m_firstBox].size = size;
	m_box.get()[m_firstBox].adrHeap = frontHeap;
	++m_numBox;
}

inline void *Heap::valueDomain(long adr) const
{
	IndexDomain *index = static_cast<IndexDomain *>(static_cast<void *>(m_box.get()[m_lastBox].adrHeap + adr));
	//IndexDomain *index = static_cast<IndexDomain *>(static_cast<void *>(m_heap.get() + adr));
	return static_cast<void *>(m_box.get()[m_lastBox].adrHeap + index->shift);
}

inline void *Heap::valueDomain(long adr, long box) const
{
	IndexDomain *index = static_cast<IndexDomain *>(static_cast<void *>(m_box.get()[box].adrHeap + adr));
	return static_cast<void *>(m_box.get()[box].adrHeap + index->shift);
}

inline void *Heap::valueDomain(long adr, Box *b) const
{
	IndexDomain *index = static_cast<IndexDomain *>(static_cast<void *>(b->value() + adr));
	return static_cast<void *>(b->value() + index->shift);
}

END_NAMESPACE_ELISA

#endif // ELISA_HEAP_H
